package com.hyb.algorithm.data.struct.dp;

import java.util.Arrays;

/**
 * @author: ybhu
 * @create: 2021/08/20 07:56
 * <p>
 *
 *
 *     300. 最长递增子序列
 *     https://leetcode-cn.com/problems/longest-increasing-subsequence/
 * 参考：https://leetcode.wang/leetcode-300-Longest-Increasing-Subsequence.html
 */
public class LengthOfLISTwo {

    public static void main(String[] args) {

        int[] nums = new int[]{10, 9, 2, 5, 3, 7, 101, 18};

        LengthOfLISTwo entity = new LengthOfLISTwo();
        System.out.println(entity.lengthOfLIS(nums));
    }

    public int lengthOfLIS(int[] nums) {

        if (nums.length <= 0) {
            return 0;
        }
        int[] dp = new int[nums.length];

        int len = 0;


        for (int i = 0; i < nums.length; i++) {

            int j = 0;

            //这里可以优化为二分法
            for (; j < len; j++) {
                if (nums[i] < dp[j]) {
                    break;
                }
            }


            //记得 此时 j 的位置
            dp[j] = nums[i];

            if (j == len) {
                len++;
            }

        }

        return len;

    }


    public int lengthOfLISWithTree(int[] nums) {

        if (nums.length <= 0) {
            return 0;
        }
        int[] dp = new int[nums.length];

        int len = 0;


        for (int i = 0; i < nums.length; i++) {

            int left = 0;
            int right = len;

            int j = 0;
            while (left < right) {
                int mid = left + (right - left) / 2;

                if (nums[i] > dp[mid]) {
                    left = mid + 1;
                } else if (nums[i] < dp[mid]) {
                    right = mid;
                }
            }


            //记得 此时 j 的位置
            dp[left] = nums[i];

            if (left == len) {
                len++;
            }

        }

        return len;

    }
}
